package com.data.basic.chapter11;

/** 利用森林结构表示结合，每一颗树表示一个集合
 * 子节点指向父亲节点 union(a,b)表示a的根节点指向b的根节点
 *
 * 基于size的优化【防止树编程链表的结构】
 * @author wang on 2018/7/4.
 */
public class UnionFind3 implements UF {
    private int [] parent;
    private int [] sz;//sz[i]表示以i为根的集合中元素的个数

    public UnionFind3(int size) {
        this.parent = new int[size];
        sz = new int[size];
        for (int i=0;i<size;i++){
            parent[i] = i;
            sz[i] = 1;//初始值为1
        }

    }
    public int getSize(){
        return parent.length;
    }

    //查找过程，查找元素p所对应的集合编号
    //查找根节点  时间复杂度O(h)
    private int find(int p){
        if (p<0||p>=parent.length){
            throw  new IllegalArgumentException("p is out of bound!");
        }
        while (p!=parent[p]){
            p = parent[p];
        }
        return p;
    }

    @Override
    public boolean isConnected(int p, int q) {
        return find(p)==find(q);
    }


    //时间复杂度O(h)
    //根据两个元素所在树的元素个数不同判断合并方向
    //将元素个数少的集合合并到元素个数多得集合中去
    @Override
    public void unionElements(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);

        if (pRoot==qRoot){
            return;
        }
        if (sz[qRoot]<sz[pRoot]){
            parent[pRoot] = qRoot;
            sz[pRoot]+=sz[qRoot];

        }else {
            parent[qRoot] = pRoot;
            sz[qRoot]+=sz[pRoot];
        }


    }
}
